#if !defined( MATRIX_COMMON_H)
#define  MATRIX_COMMON_H
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <string>

namespace bcpp_matrix
{

using std::swap;

template <class Tp>
struct bit_or : public std::binary_function<Tp,Tp,Tp> {
  Tp operator()(const Tp& x, const Tp& y) const { return x | y; }
};

template <class Tp>
struct bit_and : public std::binary_function<Tp,Tp,Tp> {
  Tp operator()(const Tp& x, const Tp& y) const { return x & y; }
};



namespace private_details
{
std::vector<std::string>& extract_clustered_names(	const std::vector<std::string>&			all_names,
													const std::vector<unsigned>&			indices,
													std::vector<std::string>&				new_names);




//________________________________________________________________________________________

//	get_single_linkage_clusters_indices

//________________________________________________________________________________________
template <typename MATRIX> 
void get_single_linkage_clusters_indices(const MATRIX& 							matrix,
										 std::vector<std::vector<unsigned> >&	clusters)
{
	//// NB cluster_ids start from 1: zero = unassigned cluster
	std::vector<unsigned>			column_to_cluster (matrix.size(), 0);
	std::vector<std::list<unsigned> >		column_clusters(1);
	unsigned					cnt_clusters = 0;

	for (unsigned column1 = 1, sz = matrix.size(); column1 < sz; ++column1)
	{
		for (unsigned column2 = 0; column2 < column1; ++column2)
		{
			if (matrix.is_missing(column1, column2))
				continue;

			unsigned& curr_cluster1 = column_to_cluster[column1];
			unsigned& curr_cluster2 = column_to_cluster[column2];

			// add new cluster if neither is yet clustered
			if (curr_cluster1 + curr_cluster2 == 0)
			{
				// cluster index for these two columns
				curr_cluster1 =
				curr_cluster2 = ++cnt_clusters;

				// these two columns make up a new cluster
				column_clusters.push_back(std::list<unsigned>());
				column_clusters.back().push_back(column1);
				column_clusters.back().push_back(column2);
			}

			// link cluster 2 to cluster 1 if both already have clusters
			else if (curr_cluster1 && curr_cluster2)
			{
				// ignore if both already part of the same cluster
				if (curr_cluster1 == curr_cluster2)
					continue;

				// assign curr_cluster1 to all of curr_cluster2 columns;
				std::list<unsigned>::iterator columns_iter = column_clusters[curr_cluster2].begin();
				std::list<unsigned>::iterator columns_end = column_clusters[curr_cluster2].end();
				unsigned old_cluster = curr_cluster2;
				while (columns_iter != columns_end)
					column_to_cluster[*columns_iter++] = curr_cluster1;

				// merge cluster 2 into cluster 1
				column_clusters[curr_cluster1].splice(column_clusters[curr_cluster1].end(),
													column_clusters[old_cluster]);
			}

			// add column 2 to cluster 1 if column 2 is unclustered
			else if (curr_cluster1)
				column_clusters[curr_cluster2 = curr_cluster1].push_back(column2);

			// add column 1 to cluster 2 if column 1 is unclustered
			else
				column_clusters[curr_cluster1 = curr_cluster2].push_back(column1);
		}
	}

	//
	// copy non-empty clusters to output set
	//
	for (unsigned i = 0; i < column_clusters.size(); ++i)
		if (!column_clusters[i].empty())
		{
			column_clusters[i].sort();
			column_clusters[i].unique();
			clusters.push_back(std::vector<unsigned>(column_clusters[i].begin(),
								   			   	column_clusters[i].end()));
		}
}



} //private_details


} // bcpp_matrix



#endif	//MATRIX_COMMON_H

